package org.hot100_1;

import java.util.ArrayList;
import java.util.List;

public class leetcode52 {

//    List<String> res= new ArrayList<>();
//    String []numString={"empty","empty","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//    StringBuilder str =new StringBuilder();
//    public List<String> letterCombinations(String digits) {
//        if (digits.length()==0){
//            return res;
//        }
//        backtracking(digits,0);
//        return res;
//    }
//
//    private void backtracking(String digits,int num){
//
//        if (str.length()==digits.length()){
//            res.add(new String(str));
//            return;
//        }
//
//        char ch = digits.charAt(num);
//        String numStr = numString[ch-'0'];
//
//        for (int i = 0; i <numStr.length(); i++) {
//            str.append(numStr.charAt(i));
//            backtracking(digits,num+1);
//            str.deleteCharAt(str.length()-1);
//        }
//
//    }

    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    String []numString={"empty","empty","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        if (digits.length()==0 || digits==null){
            return res;
        }
        backtracking(digits,0);
        return res;
    }

    private void backtracking(String digits,int num){
        if (sb.length()==digits.length()){
            res.add(new String(sb));
            return;
        }
        char ch = digits.charAt(num);
        String str = numString[ch-'0'];

        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            backtracking(digits,num+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
